Flash memory (e.g., Electrically-Erasable Programmable Read-Only Memory or “EEPROM”) has been used as long-term memory in computers, printers, and other instruments. Flash memory reduces the need for separate magnetic disk drives, which can be bulky, expensive, and subject to breakdown.
A flash memory typically includes a large plurality of floating-gate field effect transistors arranged as memory cells, and also includes circuitry for accessing the cells and for placing the transistors in one of two memory conditions (0 or 1). These transistors retain information even when power is removed, and their memory conditions can be erased electrically while the flash memory is in place.
One disadvantage of flash memory in comparison to other memories such as hard disks is that flash memory must be erased before it can be reprogrammed, while old data on a hard disk can simply be over-written when new information is to be stored thereon. Thus, when a file which is stored in flash memory changes, the changes are not written over the old data but are rather written to one or more new free blocks of the flash memory, and the old data is marked unavailable, invalid, or deleted, such as by changing a bit in a file header or in another control unit stored on the flash memory.
Because flash memory cannot be reprogrammed until it has been erased, valid information that is to be preserved in the flash memory must be rewritten to some other memory area before the area of the flash memory containing the valid information is erased. Otherwise, this valid information will be erased along with the invalid or unavailable information in the flash memory.
Older flash memories had to be erased all at one time (i.e., a portion of older flash memories could not be erased separately from other portions). Thus, with these older flash memories, a spare memory, equal in size to the flash memory, had to be available to store any valid files to be preserved while the flash memory was being erased. This spare memory could be a RAM chip, such as a static RAM or DRAM, or could comprise another flash memory. These valid files were then returned from the spare memory to the flash memory after the flash memory was erased. Accordingly, any space on the flash memory which had been taken up by the unwanted and deleted files is again made available for use.
In later flash memories, a portion of the flash memory could be erased separately from other portions of the flash memory. Accordingly, a particular target unit of the flash memory (i.e., the unit to be erased) is selected based on such criteria as dirtiness and wear leveling. Then, available free space in other blocks of the flash memory is located, and any valid data from the target unit is moved to the available space. When all valid data has been moved to the available free space, the target unit is erased (reclaimed) separately from the other units of the flash memory. This reclamation can be implemented at various times such as when there is insufficient free space to satisfy an allocation request, when the ratio of de-allocated space to block size exceeds a threshold value, when there is a need to defragment the memory, or otherwise.
Conventional flash file systems do not permit file transactions during reclamation. Accordingly, if a reclamation is underway when a power interruption occurs, valuable data could be lost since the time that any power backup is effective is limited and may be exceeded by the time required to finish the reclamation. During the next restart of the file system, the log (journal) has to be parsed and corrections will have to be applied in order to put the file system into a stable state (probably with a data loss).
Furthermore, reclamation in current flash memory file systems is based only on emulating the hard disk on linear flash without considering the rapid and deterministic storage requirements of real-time embedded applications and also without considering flash life because of (a) block device nature emulating the hard disk and (b) in-efficient wear-leveling algorithms.
The present invention provides a concurrent reclamation process that overcomes one or more of these or other problems.